package leetCode.offer32_iii;

import java.util.*;

public class Solution1 implements Solution{


    @Override
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root==null) return result;
        List<Integer> ele = new ArrayList<>();
        Queue<TreeNode> queue1 = new ArrayDeque<>();
        Queue<TreeNode> queue2 = new ArrayDeque<>();
        queue1.add(root);
        int flag = 0;
        while (queue1.size()>0) {
            TreeNode element = queue1.poll();
            ele.add(element.val);
            if(element.left!=null){
                queue2.add(element.left);
            }
            if(element.right!=null){
                queue2.add(element.right);
            }
            if(queue1.size()==0) {
                if(flag%2==1){
                    Collections.reverse(ele);
                }
                result.add(ele);
                ele = new ArrayList<>();
                Queue<TreeNode> tem = queue1;
                queue1 = queue2;
                queue2 = tem;
                flag++;
            }
        }
        return result;
    }



}
